# Definition for a binary tree node
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def rob(root):

    def dp(node):

        if not node:
            return (0, 0)
        

        left = dp(node.left)
        right = dp(node.right)
        

        selected = node.val + left[1] + right[1]

        not_selected = max(left[0], left[1]) + max(right[0], right[1])
        
        return (selected, not_selected)
    
    if not root:
        return 0
    
    result = dp(root)
    return max(result[0], result[1])


def rob_with_path(root):

    def dp_with_path(node):

        if not node:
            return ((0, []), (0, []))
        

        left = dp_with_path(node.left)
        right = dp_with_path(node.right)
        

        selected_amount = node.val + left[1][0] + right[1][0]
        selected_path = [node.val] + left[1][1] + right[1][1]
        

        left_best = left[0] if left[0][0] >= left[1][0] else left[1]
        right_best = right[0] if right[0][0] >= right[1][0] else right[1]
        not_selected_amount = left_best[0] + right_best[0]
        not_selected_path = left_best[1] + right_best[1]
        
        return ((selected_amount, selected_path), (not_selected_amount, not_selected_path))
    
    if not root:
        return (0, [])
    
    result = dp_with_path(root)
    if result[0][0] >= result[1][0]:
        return result[0]
    else:
        return result[1]
